home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_2 / qsort.fas < prev    next >
Text File  |  1995-03-23  |  5KB  |  118 lines
  1. Article 1738 of comp.sys.handhelds:
  2. From: madler@piglet.caltech.edu (Mark Adler)
  3. Newsgroups: comp.sys.handhelds
  4. Subject: A quicker quicksort on the HP-48SX
  5. Date: 5 Apr 90 19:21:50 GMT
  6. Organization: California Institute of Technology, Pasadena
  7.  
  8. With Alonzo's helpful comments about what operations are fast on the
  9. HP-48SX, and why, I wrote a quicksort program faster than Alonzo's.
  10. The speed increase comes from a different strategy (not putting the
  11. sublists on the bottom of the stack), tighter inner loops (index
  12. bounds do not have to be checked), a median approach to selecting the
  13. middle element, and a final insertion sort pass to sort short
  14. subfiles.
  15.  
  16. I tested three sorts: QSORT, ASORT, and SORT where QSORT is Alonzo's
  17. original, ASORT is QSORT modified to stop at sublists of length 24 or
  18. less and then do an insertion sort, and SORT is my version.  (SORT
  19. stops at sublists of length 20---the values 20 and 24 minimize the
  20. execution times of the respective sorts.)  They were all tested on
  21. lists of 500 reals and 50 reals (generated using RAND) with about 18K
  22. free before the list was made, and with lastargs turned off (flag -55
  23. set).  The list was stored in a global and then recalled to the
  24. stack, as per Alonzo's suggestion.  The test for 50 elements were
  25. done for 10 different random lists each and the number that follows
  26. is the standard deviation for the tests.  The times are in min:sec or
  27. just seconds:
  28.  
  29. sort       500     50
  30.  
  31. QSORT     3:55  10.37 (0.71)
  32. ASORT     3:35   7.85 (0.68)
  33. SORT      2:45   7.13 (0.31)
  34.  
  35. SORT can be modified to use a different comparison operator than ">"
  36. by changing the occurences of "IF DUP2 >" to "IF DUP2 GT", "PICK >"
  37. to "PICK GT", and "PICK <" to "PICK SWAP GT" in QPART, and "PICK >"
  38. to "PICK GT" in SORT, where GT is a program or expression that
  39. returns zero if stack entry 2 is less than or equal to stack entry
  40. one, or non-zero otherwise.
  41.  
  42. Mark Adler
  43. madler@tybalt.caltech.edu
  44.  
  45. Here are the programs:
  46.  
  47. %%HP: T(3)A(R)F(.);
  48. @ SORT crc #DBF1h length 112.5
  49. @ Use QPART to do a quicksort up to subfiles of length 20, and then do
  50. @ one pass of an insertion sort to sort the subfiles.
  51. \<< OBJ\-> \-> n                        @ put list on stack
  52.   \<< n 2 QPART                         @ do quicksort
  53.       2 n FOR j                         @ do insertion sort
  54.         j ROLL j 2 +                    @ get element j
  55.         WHILE                           @ assuming [1]..[j-1] is sorted,
  56.           DUP2 PICK >                   @  find where element j goes
  57.         REPEAT
  58.           1 -
  59.         END
  60.         2 - ROLLD                       @ put element j there
  61.       NEXT
  62.       n \->LIST                         @ convert back to list
  63.   \>>
  64. \>>
  65.  
  66. %%HP: T(3)A(R)F(.);
  67. @ QPART crc #16E0h length 389
  68. @ Given a partition of the stack, split it into two partitions so that
  69. @ all the entries in the first one are less than or equal to the entries
  70. @ in the second one, and then call this routine recusively for each of
  71. @ those partitions.  If a partition is 20 or fewer elements, then do
  72. @ nothing and end the recursion.  A final pass of an insertion sort will
  73. @ sort the remaining short partitions more efficiently.
  74. \<<
  75.   IF DUP2 - 18 > THEN                   @ sort if more than 20 elements
  76.     @ sort the portion of the stack from level l to level r (after
  77.     @  l and r are pulled off the stack).
  78.     \-> r l \<<                         @ (l is really l+1)
  79.       @ sort [l], [m], [r] so that [l] >= [m] >= [r] where they are
  80.       @  picked from the start, middle, and end of the sublist.
  81.       r l + 2 / FLOOR ROLL              @ (FLOOR needed since l is l+1)
  82.       l ROLL
  83.       IF DUP2 > THEN SWAP END
  84.       l ROLLD r ROLL
  85.       IF DUP2 > THEN
  86.         r
  87.       ELSE
  88.         SWAP r ROLLD l ROLL
  89.         IF DUP2 > THEN SWAP END
  90.         l
  91.       END
  92.       ROLLD
  93.       @ start sorting inside [l], [r].
  94.       r 3 + SWAP l 3 +
  95.       @ put [m] in list so that [i] >= [m] >= [j] for i < j.
  96.       WHILE                             @ stack is i+4,[m],j+4,list...
  97.         WHILE 1 + DUP2 PICK < REPEAT END        @ now [m] >= [i]
  98.         SWAP ROT
  99.         WHILE 1 - DUP2 PICK > REPEAT END        @ now [j] >= [m]
  100.         ROT DUP2 >                      @ until j <= i
  101.       REPEAT                            @ stack is i+4,j+4,[m],list...
  102.         DUP2 ROLL OVER ROLL             @ swap [i], [j]
  103.         4 PICK 1 + ROLLD OVER ROLLD
  104.         4 ROLLD SWAP DROP               @ stack is i+4,[m],j+4,list...
  105.       END
  106.       DROP 2 - SWAP OVER ROLLD          @ put [m] after [j]
  107.       @ sort the sublists [j+2..r] and [l..j] by calling this program
  108.       @  recursively.
  109.       r SWAP DUP 'r' STO 1 + QPART
  110.       r 2 - l QPART
  111.     \>>
  112.   ELSE
  113.     DROP2                               @ not sorting---trash r and l
  114.   END
  115. \>>
  116.  
  117.  
  118.